import java.util.BitSet;

public class MyBloomFilter {
    public static final int DEFAULT_SIZE = 1 << 20;
    // 位图
    public BitSet bitSet;
    public int usedSize;
    public static final int[] seeds = {5, 7, 11, 13, 27, 33};
    public SimpleHash[] simpleHashes;

    public MyBloomFilter(){
        bitSet = new BitSet(DEFAULT_SIZE);
        simpleHashes = new SimpleHash[seeds.length];
        for(int i = 0; i < seeds.length; i++){
            simpleHashes[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

    public void add(String val){
        for(int i = 0; i < simpleHashes.length; i++){
            int index = simpleHashes[i].hash(val);
            bitSet.set(index);
        }

        this.usedSize++;
    }

    public boolean contains(String val){
        for(int i = 0; i < simpleHashes.length; i++){
            int index = simpleHashes[i].hash(val);
            if(!bitSet.get(index)) return false;
        }

        return true;
    }
}

class SimpleHash{
    public int cap;
    public int seed;

    public SimpleHash(int cap, int seed){
        this.cap = cap;
        this.seed = seed;
    }

    public int hash(String key){
        int h;
        // (n - 1) & hash
        return (key == null) ? 0 : (seed * (cap - 1)) & ((h = key.hashCode()) ^ (h >>> 16));
    }
}
